/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/valid-sudoku
   @Language: C++
   @Datetime: 16-02-09 05:24
   */

// Method 1
class Solution {
	bool isValidCell(const vector<vector<char> > &board,int row,int col){
		if (row<0 || col <0) return 1;
		for(int i=0; i<9; ++i)  // check row, col
			if ((board[row][i]==board[row][col] && i!=col)
					||(board[i][col] == board[row][col] && i!=row))
				return false;
		for(int i=row/3*3; i<row/3*3+3; ++i) // check 3x3
			for(int j=col/3*3; j<col/3*3+3; ++j)
				if (board[i][j]==board[row][col] && i!=row &&j!=col)
					return false;
		return true;
	}

public:
	/**
	 * @param board: the board
	 * @return: wether the Sudoku is valid
	 */
	bool isValidSudoku(const vector<vector<char> > &board) {
		for (int i=0; i<9; ++i)
			for (int j=0; j<9; ++j)
				if (board[i][j]!='.' && !isValidCell(board,i,j))
					return false;
		return true;
	}
};

// Method 2 
class Solution {
	bool isValidRow(const vector<vector<char> > &board,int row){
		unordered_set<char> s;
		for (int i=0; i<9; ++i)
			if (board[row][i]!='.' && !s.emplace(board[row][i]).second)
				return false;
		return true;
	}
	bool isValidCol(const vector<vector<char> > &board,int col){
		unordered_set<char> s;
		for (int i=0; i<9; ++i)
			if (board[i][col]!='.' && !s.emplace(board[i][col]).second)
				return false;
		return true;
	}
	bool isValid33(const vector<vector<char> > &board,int row,int col){
		unordered_set<char> s;
		for(int i=row; i<row+3; ++i) // check 3x3
			for(int j=col; j<col+3; ++j)
				if (board[i][j]!='.' && !s.emplace(board[i][j]).second)
					return false;
		return true;
	}
	
public:
	/**
	 * @param board: the board
	 * @return: wether the Sudoku is valid
	 */
	bool isValidSudoku(const vector<vector<char> > &board) {
		for (int i=0; i<9; ++i)
			if (!isValidRow(board,i)) return false;
		for (int i=0; i<9; ++i)
			if (!isValidCol(board,i)) return false;
		for (int i=0; i<9; i+=3)
			for (int j=0; j<9; j+=3)
				if (!isValid33(board,i,j)) return false;
		return true;
	}
};
